 %\begin{document}
\setcounter{chapter}{1}
\setcounter{chapter}{1}
\chapter{Kĩ thuật phân hoạch, chia để trị và một số ứng dụng}
Phân hoạch(\textit{partitioning}) và chia để trị(\textit{divide-and-conquer}) là hai kỹ thuật cơ bản để xây dựng một chương trình song song. Hai kĩ thuật này có liên quan tới nhau. Trong kĩ thuật phân hoạch, bài toán được chia thành các phần riêng lẻ và mỗi phần được tính toán riêng. Kĩ thuật chia để trị thường áp dụng kĩ thuật phân hoạch trong phép đệ quy để chia liên tục bài toán thành các phần nhỏ hơn trước khi giải quyết các phần nhỏ hơn và hợp các kết quả lại.
\section{Các chiến lược phân hoạch, chia để trị}
\subsection{Kĩ thuật phân hoạch}
Phân hoạch đơn giản là chia bài toán thành các phần nhỏ. Tuy nhiên, các công thức phân hoạch đều yêu cầu kết quả của các phần nhỏ hợp lại để đạt được kết quả mong muốn.\\
\indent Kĩ thuật phân hoạch có thể được áp dụng trong dữ liệu của chương trình, tức là chia nhỏ dữ liệu và thao tác trên các dữ liệu đã chia một cách đồng thời. Việc này được gọi là chia nhỏ dữ liệu(\textit {data partitioning}) hay sự phân nhỏ miền(\textit{domain decomposition}).\\
\indent Kĩ thuật phân hoạch cũng có thể được áp dụng trong các chức năng của chương trình, tức là chia bài toán thành các chức năng độc lập và thực hiện các chức năng một cách đồng thời. Việc này được gọi là phân nhỏ chức năng(\textit{functional decomposition})\\
\subsubsection{Chia nhỏ dữ liệu}
Chia nhỏ dữ liệu là một phương pháp được dùng phổ biến và rộng rãi trong viêc tạo sự thực hiện cùng nhau trong một thuật toán thao tác trên một cấu trúc dữ liệu lớn. Ta chia dữ liệu thành các phần nhỏ, nếu được cố gắng chia thành các phần bằng nhau.
\begin{itemize}
\item Dữ liệu của bài toán có thể chia nhỏ theo nhiều cách khác nhau: theo các khối 1-chiều, 2-chiều hoặc 3-chiều.
\item Dữ liệu chia nhỏ có thể là dữ liệu đầu vào, đầu ra, hoặc dữ liệu trung gian của bài toán:\begin{itemize}
\item Chia nhỏ dữ liệu đầu ra: áp dụng cho các bài toán mà dữ liệu ra(kết quả) có thể được tính độc lập với nhau theo một hàm đầu vào.
\item Chia nhỏ dữ liệu vào: Mỗi tác vụ được tạo ra cho một phần dữ liệu vào và thực hiện các phép toán có thể trên dữ liệu cục bộ này. Khi kết quả của mỗi tác vụ không phải là kết quả cuối cùng của bài toán thì ta cần kết hợp lại.
\item Một bài toán có thể được giải quyết bằng nhiều bước và dữ liệu vào của bước này có thể là dữ liệu ra của bước tính trước đó. Việc chia nhỏ dữ liệu có thể được thực hiện ở bước trung gian.
\end{itemize}
\end{itemize}
\indent Ví dụ: Sự phân chia miền xác định của một bài toán đơn giản liên quan tới lưới điểm $3$-chiều. Việc tính toán được thực hiện bằng cách lặp lại trên mỗi điểm lưới. Trong mỗi trường hợp dữ liệu được liên quan tới một tác vụ đơn thì bôi đen.
\begin{figure}[!ht]
\centering
\includegraphics{chianho1}
\caption{\textit{Các cách chia miền xác định của một bài toán liên quan tới lưới điểm 3-chiều.}}\label{fig:Hình}
\end{figure}
\subsubsection{Chia nhỏ theo chức năng}
\begin{figure}[!ht]
\centering
\includegraphics[scale=0.75]{chianhochucnang}
\caption{\textit{Chia nhỏ theo chức năng}}\label{fig:}
\end{figure}
\indent Chia nhỏ theo chức năng ta tập trung vào việc tính toán hơn là dữ liệu đòi hỏi tính toán, nếu được thì cố gắng chia thành các tác vụ không giao nhau.\\
\indent Chia nhỏ bài toán theo chức năng thường được áp dụng cho những bài toán phức tạp mà nó là tập hợp những mô hình nối nhau về mặt hình thức.\\
\indent Có nhiều cách để chia nhỏ một bài toán, vì vậy ta cần khảo sát tất cả các cách chia có thể để có thể đưa ra cách phân chia tốt. Ta cũng có thể sử dụng kết hợp cả hai cách chia trên để có thể có cách chia nhỏ tốt hơn.\\
\indent Ví dụ: Khí hậu trái đất bao gồm mô hính khí quyển, biển, thủy học, bề mặt trái đất. Ta có thể mô phỏng khí hậu trái đất trong mô hình máy tính sử dụng phân chia miền theo chức năng. Mỗi thành phần mô hình có thể coi như là một tác vụ tách biệt và có thể song song hóa theo cách phân chia dữ liệu.
\begin{figure}[h]
\centering
\includegraphics{chianho2}
\caption{\textit{Phân chia theo chức năng trong một mô hình tính toán của khí hậu}}\label{fig:Hình}
\end{figure}
\indent Việc tìm ra các chức năng có thể thực hiện đồng thời trong một bài toán ít phổ biến hơn, nhưng chia nhỏ dữ liệu lại là chiến lược chính trong việc lập trình song song.\\
\indent Kĩ thuật chia nhỏ bài toán được áp dụng trực tiếp và hiệu quả(không phải là tối ưu) với các bài toán tính toán song song lý tưởng, tức là bài toán được chia thành các phần nhỏ hoàn toàn độc lập và có thể được thực hiện một cách đồng thời mà không yêu cầu sự truyền thông của các tiến trình riêng biệt, hoặc với các bài toán mà ở đó sự tương tác giữa các tiến trình tớ là nhỏ nhất. Với các bài toán yêu cầu sự giao tiếp của các tiến trình thì việc áp dụng trực tiếp kĩ thuật chia nhỏ không mang lại hiệu quả.\\
 Ví dụ: Tính tổng của một dãy số gồm $n$ phần tử $x_0,x_1,...,x_(n-1)$.\\
\indent Thời gian thực hiện tuần tự của bài toán là $O(n)$. Chúng ta thực hiện tính toán song song áp dụng kĩ thuật phân hoạch đơn giản bằng cách chia dãy thành $m$ phần, mỗi phần có $n/m$ phần tử, $(x_0,\ldots,x_{n/m-1})$, $(x_n/m,\ldots,x_{2n/m-1})$, ..., $(x_{(m-1)n/m},\ldots,x_{n-1})$ và sử dụng $m$ bộ xử lý (hoặc $m$) tiến trình để cộng các số của mỗi phần để tạo ra các tổng thành phần. Cuối cùng $m$ tổng thành phần này cần được cộng lại để đưa ra tổng của dãy.(Hình...)
\begin{figure}[h]
\centering
\includegraphics[scale=0.75]{chiadulieu6}
\caption{\textit{Chia nhỏ một dãy các số thành nhiều phần và tính tổng các phần}}\label{fig:Hình}
\end{figure}
Thời gian thực hiện song song của bài toán trên, $t_p=O(n+m)$. Thời gian thực hiện song song tồi hơn so với thuật toán tuần tự.\\
\subsection{Chia để trị}
Cách tiếp cận chia để trị(\textit{divide-and-conquer}) được đặc trưng bằng việc chia một bài toán thành các bài toán nhỏ hơn có cùng dạng với bài toán lớn sử dụng phương pháp đệ quy. Phương pháp đệ quy sẽ tiếp tục chia bài toán thành các tác vụ nhỏ hơn cho tới khi các tác vụ không thể nhỏ hơn được nữa. Sau đó các tác vụ đơn giản nhất được thực hiện và nối các kết quả với nhau để thực các tác vụ lớn hơn, cho đến khi thu được kết quả cuối cùng.\\
\indent JaJa(1992) đã phân biệt giữa phương pháp chia để trị và phân hoạch dựa vào công việc chính của mỗi phương pháp. Ông gọi là phương pháp chia để trị khi công việc chính là việc tổng hợp các kết quả, và gọi là phân hoạch khi công việc chính là chia nhỏ bài toán. Ở đây, chúng ta sẽ sử dụng thuật ngữ chia để trị bất cứ khi nào việc chia nhỏ còn được tiếp tục trên các bài toán nhỏ hơn.
\subsubsection{Ví dụ}
Tính tổng $S$ của dãy gồm $n$ số: $S=\sum_{i=0}^{n-1}x_i$.\\
Một định nghĩa đệ quy để cộng danh sách số(s) gồm $n$ phần tử được thể hiện như sau:\\
\hspace*{0.3in} Int add(int ${}^{*}$s)\\ 
\hspace*{0.3in} \{\\
\hspace*{0.5in} if (number(s) $=<$ 2) return (n1$+$n2);\\
\hspace*{0.5in} else \{\\
\hspace*{0.6in} divide(s, s1, s2); \hspace{0.3in} ${/}^{*}$Chia s thành 2 phần s1, s2 ${}^{*}/$\\
\hspace*{0.6in} part$\_$sum1 $=$ add(s1); \hspace{0.2in}${/}^{*}$Các lời gọi đệ quy để cộng các danh sách con${}^{*}/$\\
\hspace*{0.6in} part$\_$sum2 $=$ add(s2);\\
\hspace*{0.6in} return (part$\_$sum1$+$part$\_$sum2);\\
\hspace*{0.5in}\}\\
\hspace*{0.3in} \}\\
\indent Trong tất cả các định nghĩa đệ quy, một phương thức phải kết thúc được lời gọi đệ quy khi việc chia nhỏ không thể thực hiện được nữa. Trong mã lệnh trên, number(s) trả lại số các số trong danh sách s. Nếu có 2 số trong danh sách, hai số đó được gọi là n1 và n2. Nếu có 1 số trong danh sách thì số đó được gọi là n1, n2$=$0. Nếu không có số nào trong danh sách, thì n1$=$n2$=$0. Lời gọi đệ quy trong mã lệnh trên sẽ kết thúc trong các trường hợp có 0, 1 hoặc 2 số trong danh sách.\\
\indent Khi mỗi phép chia tạo thành 2 phần, thì kĩ thuật chia để trị đệ quy sẽ có dạng một cây nhi phân hoàn chỉnh. Với các thể hiện tuần tự, tại mỗi thời điểm ta chỉ thăm được một node của cây. Nhưng với thể hiện song song, tại một thời điểm ta có thể thăm nhiều node của cây một cách đồng thời bằng cách thực hiện như sau:
\begin{itemize}
\item Thực hiện việc chia dữ liệu trong bài toán tính tổng dãy số $x_0, x_1,\ldots, x_{n-1}$, và sử dụng 8 bộ xử lý $P_0, P_1,\ldots, P_8$. Tại mỗi giai đoạn, mỗi bộ xử lý sẽ giữ một nửa danh sách và gửi nửa còn lại cho bộ xử lý khác. Đầu tiên, $P_0$ giao tiếp với $P_4$, gửi một nửa dữ liệu tới $P_4$. Sau đó, $P_0$ và $P_4$ lại gửi một nửa dữ liệu của mình cho $P_2$ và $P_6$ một cách tương tự. Cuối cùng, $P_0, P_2, P_4$ và $P_6$ gửi một nửa dữ liệu của mình cho $P_1, P_3, P_5$ và $P_7$ một cách tương tự. Mỗi danh sách trong giai đoạn cuối sẽ có $n/8$ số hoặc $n/p$ số trong trường hợp sử dụng $p$ bộ xử lý.
\begin{figure}[!ht]
\centering
\includegraphics[scale=0.75]{chiadetri1}
\caption{\textit{Chia nhỏ một danh sách thành các phần}}\label{fig:Hình}
\end{figure}
\item Việc liên kết để tính tổng của các tổng thành phần có thể được thực hiện như hình...Khi các tổng thành phần đã được tính, mỗi tiến trình được đánh số lẻ sẽ gửi kết quả của mình cho các tiến trình được đánh số chẵn liền kề nó. Đó là, $P_1$ gửi kết quả của mình tới $P_0$, $P_3$ gửi tới $P_2$, $P_5$ gửi tới $P_4$, và $P_7$ gửi tới $P_6$. Các bộ xử lý được đánh số chẵn sau đó sẽ cộng kết quả nhận được với tổng thành phần của mình và gửi kết quả lên trên. Quá trình tiếp tục cho tới khi $P_0$ có được kết quả cuối cùng.
\begin{figure}[!ht]
\centering
\includegraphics[scale=0.75]{chiadetri2}
\caption{\textit{Tính tổng thành phần}}\label{fig:Hình}
\end{figure}
\end{itemize}
\subsubsection{Phân tích thuật toán}
Giả thiết $n$ là lũy thừa của 2, và sử dụng $p$ bộ xử lý. Thời gian thiết lập truyền thông $t_{startup}$ không được tính trong các bước.
\begin{itemize}
\item Thời gian truyền thông
\begin{itemize}
\item Trong giai đoạn chia nhỏ, ta phải thực hiện $\log_{}p$ bước chia. Thời gian truyền thông của giai đoạn này là
\[t_{comm1}=\frac{n}{2}t_{data}+\frac{n}{4}t_{data}+\cdots+\frac{n}{p}t_{data}=\frac{n(p-1)}{p}t_{data}\]
trong đó, $t_{data}$ là thời gian để chuyển một từ dữ liệu.
\item Trong giai đoạn hợp kết quả, thời gian truyền thông được tính tương tự nhưng mỗi thông điệp chỉ chứa một dữ liệu.\[t_{comm2}=t_{data}\log_{}p\]
\end{itemize}
Vậy tổng thời gian truyền thông của thuật toán là:\[t_{comm}=t_{comm1}+t_{comm1}=\frac{n(n-p)}{n}t_{data}+t_{data}\log_{}p\]
hay độ phức tạp thời gian là $O(n)$ với $p$ là hằng số.
\item Thời gian tính toán\\
Khi kết thúc giai đoạn chia nhỏ, việc tính tổng của $n/p$ số được thực hiện ở mỗi bộ xử lý. Và trong giai đoạn hợp kết quả mỗi bước chỉ thực hiện một phép cộng. Thời gian tính toán của thuật toán:
\[t_{comp}=\frac{n}{p}+ logp\]
hay độ phức tạp thời gian là $O(n)$ khi $p$ là hằng số. Với $n$ lớn và $p$ là biến thì ta sẽ lấy độ phức tạp thời gian là $O(n/p)$.
\end{itemize}
Tổng thời gian thực hiện song song của thuật toán là 
\[t_p=\frac{n(n-p)}{p}t_{data}+t_{data}\log_{}p+\frac{n}{p}+\log_{}p\]

\subsection{Chia để trị $m$-nhánh}
Kĩ thuật chia để trị cũng có thể được áp dụng vào các bài toán mà khi một tác vụ được chia nhỏ thành nhiều hơn hai phần ở mỗi bước. Ví dụ một tác vụ được chia nhỏ thành bốn phần, định nghĩa đệ quy tuần tự có thể là\\
\hspace*{0.3in} Int add(int ${}^{*}$s)\\ 
\hspace*{0.3in} \{\\
\hspace*{0.5in} if (number(s) $=<$ 4) return ($n1+n2+n3+n4$);\\
\hspace*{0.5in} else \{\\
\hspace*{0.6in} divide(s, s1, s2, s3, s4); \hspace{0.3in} ${/}^{*}$Chia s thành 2 phần s1, s2, s3, s4 ${}^{*}/$\\
\hspace*{0.6in} part$\_$sum1 $=$ add(s1); \hspace{0.2in}${/}^{*}$Các lời gọi đệ quy để cộng các danh sách con${}^{*}/$\\
\hspace*{0.6in} part$\_$sum2 $=$ add(s2);\\
\hspace*{0.6in} part$\_$sum3 $=$ add(s3);\\
\hspace*{0.6in} part$\_$sum4 $=$ add(s4);\\
\hspace*{0.6in} return (part$\_$sum1$+$part$\_$sum2$+$part$\_$sum3$+$part$\_$sum4);\\
\hspace*{0.5in}\}\\
\hspace*{0.3in} \}\\
\begin{figure}[ht]
\centering
\includegraphics[scale=0.65]{quadtree}
\caption{\textit{Quadtree và ứng dụng để chia miền 2-chiều}}\label{fig:Hình}
\end{figure}
Cây $m$-nhánh được hình thành nếu phép chia là phép chia nhỏ thành $m$ phần. Cây $m$-nhánh có những ứng dụng cụ thể riêng.\\
Trong cây mỗi node cha có bốn node con, gọi là \textit{quadtree} được ứng dụng để chia các miền $2-$chiều thành bốn miền con (Hình...); \textit{octree} là cây trong đó mỗi node cha có tám node con được ứng dụng trong việc chia không gian $3-$chiều đệ quy (Hình...).\\
\begin{figure}[ht]
\centering
\includegraphics[scale=0.5]{octree}
\caption{\textit{Octree và ứng dụng để chia không gian 3-chiều}}\label{fig:Hình}
\end{figure}
Thuật toán xây dựng cây quadtree(octtree được làm tương tự).\\
\textit{Procedure Quad$\_$Tree$\_$Build \\
    Quad$\_$Tree $=$ {empty}\\
    for j $=$ 1 to N                               … vòng lặp với tất cả N hạt\\
         Quad$\_$Tree$\_$Insert(j, root)        … chèn hạt i vào QuadTree\\
    endfor\\
    …   Tại điểm này, mỗi lá của Quad$\_$Tree sẽ có 0 hoặc 1 hạt\\ 
    …   có 0 hạt nếu các node chị em ruột có 1 hạt\\
    Duyệt cây Quad$\_$Tree xóa bỏ các lá rỗng  … sử dụng, Breadth First Search\\
\\
Procedure Quad$\_$Tree$\_$Insert(j, n) … Chèn hạt thứ j vào node thứ n trong cây Quad$\_$Tree\\
    if n là node trong              … n có 4 node con\\
        xác định node con c của node n chứa hạt j\\
        Quad$\_$Tree$\_$Insert(j, c)\\
   else if n chứa 1 hạt   …  n là node lá\\
        thêm 4 node con của n vào the Quad$\_$Tree
        chuyển hạt trong n tới node con chứa nó\\
        đặt c là node con của n chứa j\\
        Quad$\_$Tree$\_$Insert(j, c)\\
    else                                         …  n rỗng \\
        lưu hạt j ở node n\\
    end\\}

\section{Một số ứng dụng trong thuật toán song song}
\subsection{Nhân ma trận với vecto}
Trong phần này chúng ta sẽ ứng dụng kĩ thuật chia nhỏ dữ liệu để thiết kế thuật toán song song cho bài toán nhân ma trận vuông dày $A$ cỡ $n\times n$ với vecto $x$ cỡ $n\times 1$, cho ra kết quả là vecto $y$.\\
Thuật toán tuần tự thông thường để nhân một ma trận với vecto:\\
\hspace*{1cm}MAT$\_$VECT$(A, x, y)$\{\\
\hspace*{2cm} for$( i=0; i<n; i++)$\{\\
\hspace*{3cm} $y[i]=0$;\\
\hspace*{3cm} for$(j=0; j<n-1; j++)$ do\\
\hspace*{4cm} $y[i]=y[i]+A[i,j]*x[j]$;\\
\hspace*{3cm}\}\\
\hspace*{2cm}\}\\
Độ phức tạp của thuật toán là $O(n^2)$.
\subsubsection{Chia nhỏ dữ liệu đầu vào theo khối 1-chiều}
Trong phần này trình bày thuật toán song song cho phép nhân ma trận với vecto sử dụng kĩ thuật chia nhỏ dữ liệu theo khối 1-chiều.\\
\begin{figure}[!ht]
\centering
\includegraphics[scale=0.75]{matvec}
\caption{\textit{Phép nhân ma trận cỡ $n\times n$ với vecto $n$ sử dụng kĩ thuật chia nhỏ thành các khối theo hàng trong trường hợp $p=n$}}\label{fig:}
\end{figure}
Ta chia nhỏ ma trận $A$ và vecto $x$ thành các khối theo hàng.
\paragraph{Gán mỗi hàng cho một tiến trình} Trong trường hợp này, ma trận $A$ được chia nhỏ cho $p$ ($p=n$) tiến trình và một phần tử của vecto $x$. Tiến trình $P_i$ sở hữu hàng $A[i]$ và phần tử $x[i]$ sẽ tính $y[i]$. Để tính $y[i]$, tiến trình $P_i$ cần toàn bộ vecto $x$ nên thuật toán gồm hai bước sau:\begin{enumerate}
\item  Mỗi tiến trình bắt đầu chỉ có một phần tử của $x$, sử dụng hàm loan tin all-to-all để phân bố phần tử đó đến tất cả các tiến trình còn lại.
\item Tiến trình $P_i$ tính $y[i]=\sum_{j=0}^{n-1}(A[i, j]*x[j])$.
\end{enumerate}
\indent \textbf{Thời gian thực hiện song song}
\begin{itemize}
\item [\ $t_{comm}$]:  Là toàn bộ bước 1, có \[t_{comm}=O(n)\]
\item [\ $t_{comp}$]: Là thời gian thực hiện bước 2, có \[t_{comp}=O(n)\]
\end{itemize}
Vậy độ phức tạp thời gian của thuật toán khi sử dụng $n$ tiến trình là $O(n)$.
\paragraph{Sử dụng $p$ tiến trình, $p<n$} Mỗi tiến trình sẽ chứa $n/p$ hàng của ma trận $A$, và một phần của vecto $x$ cỡ $n/p$. Tương tự như trong phần trên, trong bước 1 ta sử dụng hàm loan tin all-to-all tới $p$ tiến trình và mỗi thông điệp bao gồm $n/p$ dữ liệu, $t_{comm}=t_{startup}\log_{}{b}+(p-1)(n/p)t_{data}$, với $p$ lớn ta có thể xấp xỉ bằng $t_{startup}\log_{}{p}+nt_{data}$. Trong bước 2, cần thực hiện tính $n/p$ hàng của ma trận $A$ lần lượt với vecto $x$ tương ứng, yêu cầu $n^2/p$ thời gian.\\
\indent Vậy tổng thời gian thực hiện song song khi sử dụng $p$ tiến trình là
\[t_p=n^2/p + t_{startup}\log_{}{b}+(p-1)(n/p)t_{data}\]
\subsubsection{Chia nhỏ thành các khối 2-chiều}
Trong phần này ta nghiên cứu thuật toán nhân ma trận với vecto bằng việc chia nhỏ ma trận thành các khối 2-chiều và gán vào cho các tiến trình. Hình 2.10 miêu tả thuật toán song song.
\begin{figure}[!ht]
\centering
\includegraphics[scale=0.75]{matvec2}
\caption{\textit{Phép nhân ma trận-vecto sử dụng chia nhỏ thành khối 2-chiều}}\label{fig:}
\end{figure}
\paragraph{Gán mỗi phần tử cho một tiến trình}
Ma trận được chia nhỏ thành $n^2$ khối, ta sử dụng $n^2$ tiến trình để gán mỗi phần từ cho một tiến trình, mỗi phần tử của vecto $x$ được lưu ở $n$ tiến trình ở cột cuối cùng của . Thuật toán song song được thực hiện theo 4 bước sau:\begin{enumerate}
\item Các phần tử vecto chứa trong n tiến trình nằm ở cột cuối cùng được phân phối tới tiến trình trong cùng hàng nằm trên đường chéo chính sử dụng hàm loan tin one-to-one. Thời gian yêu cầu là $O(\log_{}{n})$).
\item Các tiến trình nằm trên đường chéo chính sử dụng hàm loan tin one-to-all để phân phối phần tử của $x$ trong tới tất cả các tiến trình còn lại trong cùng một cột một cách đồng thời. Thời gian yêu cầu là $O(\log_{}{n})$.
\item Mỗi tiến trình $P_{i,j}$thực hiện phép nhân phần tử $A[i,j]$ với $x[j]$ tương ứng một cách đồng thời. Thời gian yêu cầu là $O(1)$.
\item Sử dụng hàm gộp all-to-one để tính tổng của mỗi hàng, địa chỉ đến là tiến trình nằm ở cột cuối cùng. Thời gian yêu cầu là $O(\log_{}{n})$. 
\end{enumerate}
\indent Vậy, tổng thời gian thực hiện song song của thuật toán \[t_p=O(\log_{}{n})\] Nhưng chi phí để thực hiện \[Cost=O(n^2\log{}{n})\] đây không phải là thuật toán có chi phí tốt nhất.
\subsubsection{Sử dụng ít hơn $n^2$ tiến trình}
Ta chia ma trận thành $p$ khối, mỗi khối cỡ $n/(\sqrt{p})\times n/(\sqrt{p})$.
Giả sử, ta sử dụng một mảng lưới hai chiều gồm $p$ tiến trình để lưu mỗi khối của ma trận. Vecto $x$ được chia nhỏ thành $\sqrt{p}$ phần, mỗi phần gồm $n/(\sqrt{p})$ phần tử và được lưu tại tiến trình của cột cuối cùng($\sqrt{p}-1$). Thuật toán được thực hiện như sau:\begin{enumerate}
\item Gán các phần của vecto dọc theo đường chéo chính. Để làm việc này, mỗi tiến trình nằm trên
cột bên phải nhất của lưới 2-chiều gửi $n/(\sqrt{p})$ của mình tới một tiến trình trong cùng hàng nằm trên đường chéo chính. Thời gian yêu cầu trong bước này là $t_{startup}+(n/(\sqrt{p}))t_{data}$.
\item Mỗi tiến trình trên đường chéo chính sử dụng hàm loan tin one-to-all theo cột để phân phối $n/(\sqrt{p})$ phần tử vecto. Thời gian yêu cầu là $(t_{startup}+(n/(\sqrt{p})))\log_{}{\sqrt{p}}$.
\item Mỗi tiến trình thực hiện $n^2/p$ phép nhân để tính tại khối và cộng cục bộ $n/(\sqrt{p})$ phân tử với nhau. Kết thúc bước này mỗi tiến trình sẽ có $n/(\sqrt{p})$ tổng thành phần.
\item Cộng gộp $n/(\sqrt{p})$ giá trị của mỗi hàng lại sử dụng hàm gộp all-to-one, địa chỉ đến là cột bên phải nhất của lưới. Thời gian yêu cầu (bỏ qua thời gian thực hiện phép cộng) là $(t_{startup}+(n/(\sqrt{p})))\log_{}{\sqrt{p}}$.
\end{enumerate}
\indent Thời gian thực hiện song song của thuật toán:
\[t_p=n^2/p + t_{startup}+(n/(\sqrt{p}))t_{data} + 2(t_{startup}+(n/(\sqrt{p})))\log_{}{\sqrt{p}}\]
\[\approx n^2/p + t_{startup}\log_{}{p} + \log_{}{p}n/(\sqrt{p})t_{data}\]


\subsection{Thuật toán sắp xếp}
\subsubsection{Sắp xếp theo giỏ(\textit{Bucket sort})}
Các thuật toán sắp xếp đã được nghiên cứu nhiều trong lập trình tuần tự. Hầu hết các thuật toán sắp xếp tuần tự đều dựa trên cơ sở so sánh và đổi chỗ các cặp số. Phần này chúng ta sẽ sử dụng kĩ thuật phân hoạch và chia để trị để song song hóa thuật toán sắp xếp theo giỏ(\textit{bucket sort}).\\
\indent Thuật toán bucket sort không dựa trên cơ sở so sánh và đổi chỗ, thuật toán là một phép phân hoạch một cách tự nhiên. Thuật toán bucket sort chỉ có hiệu quả khi các số ban đầu có phân bố đều trên một khoảng cho trước, giả sử từ $0$ đến $a-1$. Khoảng cho trước sẽ được chia thành $m$ khoảng nhỏ, $0$ tới $a/m-1$, $a/m$ tới $2a/m-1$,$\ldots$, và mỗi giỏ được gán để chứa các số trong khoảng đó, vậy cần có $m$ giỏ.
\subsubsection{thuật toán tuần tự}
\begin{itemize}
\item Đặt các số vào các khoảng phù hợp: Để đặt một số vào khoảng thích hợp, ta có thể so sánh số đó với các các số $a/m, 2a/m, 3a/m,\ldots$, sẽ cần nhiều $m-1$ bước so sánh để đặt được một số vào dãy thích hợp. Hoặc ta có thể chia số đó cho m, sử dụng kết quả để đặt vào các giỏ tương ứng từ $0$ đến $m-1$. Nếu $m$ là lũy thừa của 2 ta có thể sử dụng các bit trên đầu của mỗi số dưới dạng nhị phân. Trong bất kì cách nào, ta giả sử để đặt một số vào giỏ cần 1 bước. Vậy để đặt tất cả các số cần $n$ bước.
\begin{figure}[ht]
\centering
\includegraphics[scale=0.75]{bucket1}
\caption{\textit{Sắp xếp theo giỏ}}\label{fig:Hình}
\end{figure}
\item Các số trong mỗi giỏ sẽ được sắp xếp bởi một thuật toán sắp xếp tuần tự: Giả sử thuật toán sắp xếp tuần tự sử dụng để sắp ở mỗi giỏ đòi hỏi $n\log_{}n$ phép so sánh, mỗi phép so sánh tương đương với một bước tính toán. Vậy để sắp xếp $n/m$ số ở mỗi giỏ cần $(n/m)\log_{}{(n/m)}$ bước.
\item Nối các số trong giỏ đã sắp để đưa ra dãy đã sắp cuối cùng: không sử dụng tính toán.
\end{itemize}
Vậy thời gian xử lý tuần tự là
\[t_s=n+m((n/m)\log_{}{(n/m)})=n+n\log_{}{(n/m)}=O(n\log_{}{(n/m)})\]
Nếu $n=km$, $k$ là hằng số thì độ phức tạp thời gian là $O(n)$.

\subsubsection{Thuật toán song song}
Một cách đơn giản thuật toán bucket sort có thể được song song bằng cách gán mỗi bộ xử lý cho một giỏ. Khi đó, thời gian sắp xếp ở mỗi giỏ sẽ là $(n/p)\log_{}{n/p}$ với $p$ bộ xử lý (trong đó $p=m$).\\
Ta có thể cải thiện thuật toán song song trên để đạt hiệu quả hơn bằng cách phân hoạch dãy số thành $m$ miền, và mỗi miền ứng với một bộ xử lý. Mỗi bộ xử lý giữ $p$ giỏ nhỏ và tách các số trong miền của nó vào từng rỏ riêng của mình. Sau đó các giỏ nhỏ này sẽ được "trút" vào $p$ giỏ cuối cùng để sắp xếp, việc này yêu cầu mỗi bộ xử lý gửi một giỏ nhỏ tới mỗi bộ xử lý khác(giỏ thứ $i$ tới bộ xử lý thứ $i$).
\begin{figure}[!ht]
\centering
\includegraphics[scale=0.75]{bucket2}
\caption{\textit{Thuật toán bucket sort song song}}\label{fig:Hình}
\end{figure}
\paragraph{Phân tích} Thuật toán gồm 4 giai đoạn sau đây:
\begin{enumerate}
\item Phân các số vào $p$ miền.\\
Giả sử cần $n$ bước tính toán để phân $n$ số vào $p$ miền. \[t_{comp1}=n\]
Sau khi chia nhỏ, $p$ phần nhỏ mỗi phần chứa $n/p$ số được gửi tới các tiến trình.
\[t_{comm1}=t_{startup}+t_{data}n\]
\item Sắp xếp trong các giỏ nhỏ.\\
Chia mỗi phần của $n/p$ số vào $p$ giỏ nhỏ yêu cầu thời gian là \[t_{comp2}=n/p\]
\item Gửi tới các giỏ lớn.\\
Các giỏ nhỏ được phân tán. Mỗi giỏ nhỏ có khoảng $n/{p^2}$ số (giả thiết là phân bố đều). Mỗi tiến trình phải gửi $(p-1)$ giỏ nhỏ tới các tiến trình khác. Cả p tiến trình phải thực hiện phép truyền thông này, ta có \[t_{comm3}=p(p-1)(t_{startup}+(n/{p^2})t_{data})\] nếu các phép truyền thông này không thể gối nhau về thời gian và sử dụng các hàm gửi riêng . Nếu tất cả phép truyền thông được gối đầu nhau, có \[t_{comm3}=(p-1)(t_{startup}+(n/{p^2})t_{data})\]
\item Sắp xếp trong giỏ lớn.\\
Trong giai đoạn này, các giỏ lớn được sắp đồng thời, do đó \[t_{comp4}=(n/p)\log_{}{(n/p)}\]
\end{enumerate}
Vậy tổng thời gian thực hiện là
\[t_p=t_{startup}+t_{data}n+(p-1)(t_{startup}+(n/{p^2})t_{data})+(n/p)\log_{}{(n/p)}\]
Công thức trên đạt được khi các số được phân bố đều. Nếu các số không có phân bố đều thì số các số trong mỗi giỏ sẽ khác nhau, điều này sẽ làm tăng tổng thời gian tính toán. Trường hợp tồi nhất của bài toán là khi tất cả các số cùng nằm trong một giỏ.
\indent Thuật toán bucket sort có thể được phát triển theo phương pháp chia để trị bằng cách chia liên tục các giỏ cho tới khi mỗi giỏ chỉ chứa một phần tử của dãy. Phương pháp này tương tự như thuật toán quick sort(sắp xếp nhanh), chỉ khác là trong quick sort sử dụng một phần tử để chia đôi miền.
\subsubsection{Sắp xếp nhanh(\textit{Quick sort})}
Quick sort là một thuật toán sắp xếp tuần tự nổi tiếng dựa trên phương pháp chia để trị. Độ phức tạp thời gian trung bình của thuật toán là $O(n\log_{}{n})$.Ý tưởng của thuật toán là chia đôi dãy cần sắp thành hai dãy con rời nhau sao cho chỉ cần sắp xếp trên các dãy con. Để làm được điều này ta cần chọn một phần tử hoa tiêu(\textit{pivot}), so sánh các số trong dãy với phân tử này, các phần từ nhỏ hơn và phần tử chốt được đặt vào một danh sách con, phần còn lại vào một danh sách con khác. Quá trình này lặp lại cho tới khi những danh sách cuối cùng chỉ còn một phần tử.
\paragraph{Thuật toán tuần tự} Thường được miêu tả bằng một thủ tục đệ quy. Giả sử, cần sắp xếp một mảng list[ ] chứa các số, pivot là chỉ số của phần tử trong mảng được chọn làm hoa tiêu.\\
\hspace*{1cm}Quicksort(list, start, end)\{\\
\hspace*{2cm} if(start$<$end)\{\\
\hspace*{3cm} Partition(list, start, end, pivot);\\
\hspace*{3cm} Quicksort(list, start, pivot);\\
\hspace*{3cm} Quicksort(list, pivot, end);\\
\hspace*{2cm}\}\\
\hspace*{1cm}\}\\
Trong đó, Partition() là hàm chuyển các phần tử nhỏ hơn hoặc bằng pivot về phía trước, phần tử lớn hơn pivot về phía sau.
\begin{figure}[!ht]
\centering
\includegraphics[scale=0.55]{quicksort}
\caption{\textit{Thuật quicksort song song với các pivot}}\label{fig:}
\end{figure}

\paragraph{Song song hóa thuật toán quick sort} Thuật toán quick sort có thể được song song một cách đơn giản như sau: Bắt đầu thực hiện ở một bộ xử lý và chuyển lời gọi đệ quy tới toàn bộ các bộ xử lý còn lại. Cách làm này sẽ tạo ra một cấu trúc cây nhị phân như hình 2.13\\
\indent Thuật toán có thể được phát biểu lại như sau:\begin{enumerate}
\item Chọn phần tử pivot để chia danh sách thành hai dãy con.
\item Chèn pivot vào giữa hai dãy con được tách ra và nó là vị trí đầu tiên được sắp sau khi thực hiện bước một.
\item Lặp lại bước 1 một cách đệ quy cho tới khi mỗi dãy gồm một phân tử.
\end{enumerate}
Danh sách đã sắp có thể đạt được bằng cách tìm kiếm cây theo thứ tự giữa trước (nút trái- nút cha- nút con)

\indent \textbf{Đánh giá thuật giải song song}\\
Giả thiết pivot đươc chọn một cách lý tưởng tức mỗi lần chia dãy tạo ra hai dãy con có kích cỡ bằng nhau.
\begin{itemize}
\item[\ $t_{comp}$]: đầu tiên, một bộ xử lý thao tác với $n$ số, tiếp theo 2 bộ xử lý thao tác với $n/2$ bộ xử lý,...Vậy \[t_{comp}=n+\frac{n}{2}+\frac{n}{4}+\ldots \approx 2n\]
\item[\ $t_{comm}$]: Giả sử ta sử dụng $p$ tiến trình, ta cần $\log_{}{p}$ phép chia. Vậy
\[t_{comm}=(t_{startup}+(n/2)t_{data})+t_{startup}+(n/4)t_{data})+t_{startup}+(n/8)t_{data})+\ldots\]
\[=(\log_{}{p})t_{startup}+nt_{data}\]
\end{itemize}

\subsection{Bài toán N-body}
Bài toán $N$-body quan tâm tới các lực giữa các hạt/vật thể trong không gian. Mỗi một cặp các hạt này sinh ra một lực nào đó, vì vậy ta giả sử có $N$ hạt thì mỗi một hạt sẽ chịu tác động của $N-1$ lực khác nhau, $N-1$ lực này tổng hợp lại tạo thành một lực tổng hợp. Hợp lực này làm tăng tốc của hạt.\\
Bài toán $N$-body có thể được định nghĩa như sau: Trong một hệ thống gồm nhiều vật thể, giả sử ta đã biết trạng thái ban đầu của tất cả các vật thể trong hệ thống, ví dụ như vận tốc và vị trí ban đầu. Ta phải đánh giá tất cả các lực tương tác giữa các vật thể để nhận được vận tốc mới và vị trí mới của các vật thể trong hệ thống. Vì vậy, bằng việc thực hiện lặp lại các đánh giá này chúng ta có được thông tin về sự biến đổi theo thời gian của hệ thống.\\
Bài toán $N$-body xuất hiện trong việc nghiên cứu lý thuyết cấu trúc quy mô lớn như vũ trụ, các thiên hà, các chùm sao, hệ mặt trời, các động lực học tinh tế, mô hình khí hậu, khí đốt, chất lỏng và plasma; trong các quy mô nhỏ hơn như các hiệu ứng lượng tử. Bài toán $N$-body cũng được ứng dụng trong việc mô phỏng các phân tử sinh vật lớn như sự mở ra của protein hiện thực và axit deoxyribonucleic(DNA).\\
Thuật toán cơ bản cho bài toán $N$-body như sau:\\
    \textit{$t = 0$\\
 \hspace*{0.5cm}    while $t < t_final$\\
 \hspace*{1cm}        for $i = 1$ to N          ... N $=$ số các hạt\\
 \hspace*{1.5cm}            tính f(i) $=$ lực tác dụng lên hạt i\\
 \hspace*{1.5cm}            sự di chuyển của hạt i dưới tác dụng của f(i) trong thời gian dt\\
 \hspace*{1cm}        end for\\
 \hspace*{1cm}        tính các đặc trưng cần quan tâm của các hạt\\
 \hspace*{1cm}        $t = t + dt $             ... dt $=$ thời gian gia tăng\\
 \hspace*{0.5cm}     end while\\}
Thuật toán yêu cầu $N^2$ phép tính. Giả sử chúng ta cần xác định vị trí của các vật thể trong vũ trụ, giả thiết có $10^{11}$ vật thể, nó cần lặp lại $10^{22}$ phép tính. Nếu máy tính thời gian xử lý một phép toán của máy tính tuần tự là $1\mu s$ thì mất khoảng $10^9$ năm để lặp lại một quá trình tính toán.\\
Để giảm số lượng các hạt trong tổng lực, chúng ta có thể sử dụng quan sát sau: một cụm các hạt ở xa có thể được xấp xỉ bằng một điểm đơn có khối lượng bằng tổng của tất cả các hạt trong cụm và có tâm đặt tại tâm của cụm.
\begin{figure}[!ht]
\centering
\includegraphics[scale=0.85]{cluster}
\caption{\textit{Xấp xỉ cụm các hạt bằng một điểm đơn}}\label{fig:Hình}
\end{figure}
Xét một thuật toán tuần tự dựa trên quan sát trên đó là, thuật toán Barnes-Hut.
\subsubsection{Thuật toán Barnes-Hut}
Thuật toán Barnes-Hut là lời giải phân cấp đơn giản nhất cho bài toán $N$-body, được ứng dụng nhiều trong vật lý học thiên thể(astrophysic). Thuật toán được J.Barnes và P.Hut đưa ra lần đầu tiên vào năm 1986 dựa trên thuật toán do A.Apel đưa ra năm 1985.
Thuật toán sử dụng phép xấp xỉ cụm với dạng một cách chia để trị khéo.\\
Thuật toán coi toàn bộ không gian là một hình lập phương có chứa tất cả các vật thể. Đầu tiên, hình lập phương này được chia thành 8 hình lập phương con, nếu hình lập phương con không chứa hạt sẽ bị xóa từ cha tương ứng. Nếu hình lập phương chứa nhiều hơn một hạt sẽ được chia tiếp tục cho tới khi mỗi hình lập phương chỉ chứa một hạt. Cách chia này tạo thành octtree, các lá là các hình lập phương chứa một hạt.\\
Đối với bài toán thuộc không gian hai chiều, ta sẽ chia không gian thành 4 phần, mỗi phần con được chia liên tục cho tới khi mỗi vùng chỉ chứa một vật thể, tạo thành quadtree.\\
\indent Sau khi cây được xây dựng, tổng khối lượng và tâm của số các vật thể chứa trong hình lập phương con được lưu tại node đó. Lực tác dụng lên vật thể có thể tính được bằng cách duyệt cây bắt đầu tại gốc, và dừng tại node mà tại đó phép xấp xỉ có thể sử dụng cho một vật thể cụ thể, trong trường hợp còn lại thì tiếp tục duyệt cây theo chiều từ trên xuống.\\
\indent Trong bài toán N-body lớn, một tiêu chuẩn được sử dụng để phép xấp xỉ có thể được thực hiện là: Giả sử cụm các vật thể nằm trong một khối lập phương có thể tích là $d\times d\times d$, khoảng cách tới tâm của cụm là $r$. Ta có thể sử dụng phép xấp xỉ khi
\[ r\geq {\frac{d}{\theta}}\] trong đó, $\theta$ là hằng số không đổi, $\theta \leq 1$.\\
Tổng khối lượng $TM$ tại một node là tổng của khối tại các node con, \[TM=\mathop{\pmb{\sum}}_{i=0}^{k}m_i\]
trong đó, $m_i$ là tổng khối lượng tại node con thứ $i$. Tâm khối, $TC$, được tính bằng công thức 
\[TC=\frac{1}{TM}\mathop{\pmb{\sum}}_{i=0}^{k}(m_i\times c_i)\]
trong đó, $c_i$ là tâm khối của con thứ $i$. $k=4$ nếu sử dụng cây quadtree, $k=7$ nếu sử dụng cây octtree.\\
Khi tất cả các vật thể có vận tốc và vị trí mới, thì quá trình tính toán được lặp lại với mỗi khoảng thời gian.\\
\indent Thuật toán tuần tự Barnes-Hut có thể được miêu tả như sau như sau:\begin{enumerate}
\item Xây dựng cây quadtree/octtree gồm các thủ tuc: dựng cây, và chèn thêm node vào cây đã trình bày ở phần trên.
\item Tính khối lượng $TM$ và tâm của khối $CM$ tại mỗi node.\\
\textit{( TM, CM )$ =$ Compute$\_$Mass( root )\\
\hspace*{0.5cm} function ( TM, CM ) $=$ Compute$\_$Mass( n )    … Tính CM và TM của node n
\hspace*{0.5cm}     if n chứa 1 hạt\\
\hspace*{1cm}          … TM and CM bằng khối lượng và vị trí của hạt\\
\hspace*{1cm}            lưu (TM, CM) tại node n\\
\hspace*{1cm}         return (TM, CM)\\
\hspace*{0.5cm}       else       … “post order traversal”: tính toán tại tất cả node con trước\\
 \hspace*{1cm}           for tất cả node con c(j) of n  … j $=$ 1,2,3,4\\
 \hspace*{1.5cm}                 ( TM(j), CM(j) ) $=$ Compute$\_$Mass( c(j) )\\
  \hspace*{1cm}          endfor\\
  \hspace*{1cm}          $TM = TM(1) + TM(2) + TM(3) + TM(4)$  \\
  \hspace*{1cm}          $CM = ( TM(1)*CM(1) + TM(2)*CM(2) + TM(3)*CM(3) + TM(4)*CM(4) ) / TM$\\
   \hspace*{1cm}         lưu ( TM, CM ) tại node n\\
  \hspace*{1cm}          return ( TM, CM )\\
 \hspace*{0.5cm}      end if\\}
\item Tại mỗi node ta cần duyệt lại cây để tính tổng lực tác động lên nó.\\
\textit{ 
\hspace*{0.5cm}for k $=$ 1 to N\\
\hspace*{1cm}  f(k) $=$ TreeForce( k, root )  \\ 
\hspace*{1cm}              … tính lực tác dụng lên hạt k do tất cả các hạt tại nút gốc gây ra\\
 \hspace*{0.5cm}endfor\\
\hspace*{0.5cm}function f $=$ TreeForce( k, n )  … tính lực tác dụng lên node k của tất cả các hạt chứa trong node n\\
\hspace*{1cm}    f $=$ 0\\
\hspace*{1cm}  if n chứa 1 
\hspace*{1.5cm}     tính f theo công thức trực tiếp\\
\hspace*{1cm}  else\\
\hspace*{1.5cm}        r $=$ khoảng cách từ k tơi tâm của các hạt trong node n\\
\hspace*{1.5cm}        d $=$ cỡ của node n\\
\hspace*{1.5cm}       if  $d/r < \theta$     … sử dụng phép xấp xỉ cụm\\
\hspace*{2cm}          tính f sử dụng công thức xấp xỉ\\
\hspace*{1.5cm}        else              … cần xem xét bên trong node\\
\hspace*{2cm}           for mỗi node con c của node n\\
\hspace*{2.3cm}                 $f = f + TreeForce ( k, c )$\\
\hspace*{2cm}         end for\\
\hspace*{1.5cm}   end if\\
 \hspace*{1cm}   end if\\}
\end{enumerate}
Độ phức tạp thời gian của thuật toán Barnes-Hut là $O(n\log_{}{n})$[1]\\
\indent Đây là một ví dụ ứng dụng thành công thuật toán Barnes-Hut trong bài toán nghiên cứu sự hình thành và phân bố thống kê của các thiên hà trong vật lý học thiên thể. Các mô phỏng bào gồm 17 triệu ngôi sao trong hơn 600 nhịp thời gian. Thuật toán thực hiện hết 24 giờ trên một máy Intel Delta 512 bộ xử lý, tốc độ tính toán của mỗi bộ xử lý là 10 Mflops, tốc độ tính toán của máy là khoảng trên 5 Gflops. Trong khi đó nếu sử dụng thuật toán tuần tự $O(n^2)$ trên máy tính như trên thì thời gian thực hiện là khoảng một năm[1].
\subsubsection{Song song hóa thuật toán Barnes-Hut}
Thuật toán Barnes-Hut có thể được song song tốt trên cả hai loại máy tính chia sẻ và phân tán bộ nhớ. Ta sử dụng hai chiến lược được gọi là phân vùng không gian(\textit{spatial partitioning}) và phân vùng cây(\textit{tree partitioning}).
\paragraph{Spatital partitioning} Phương pháp này chia không gian chứa các hạt thành các hình chữ nhật(trong không gian 2-chiều) không gối lên nhau với số hạt trong mỗi phần bằng (hoặc xấp xỉ) nhau, và gán mỗi phần cho một bộ xử lý/tiến trình, làm việc tốt khi là không gian 2-chiều. Phương pháp này được gọi là phương pháp chia đôi đệ quy trực giao(\textit{Orthogonal Recursive Bisection, ORB}).\\
\indent Đầu tiên, một đường thẳng đứng sẽ chia không gian thành hai phần với số hạt bằng nhau. Số các hạt trong mỗi phần được chia thành 2 phần bởi 2 đường nằm ngang. Quá trình này tiếp tục cho tới khi số các vùng bằng số các bộ xử lý được sử dụng.\\
\indent Để bộ xử lý $k$ chạy thuật toán Barnes-Hut trên các hạt được lưu ở bộ xử lý, bộ xử lý k cần truy cập vào một cây con của Quadtree để tính các lực tác dụng lên mỗi hạt, cây này được gọi là cây địa phương quan trọng(\textit{Locally Essential Tree, LET}). LET bao gồm toàn bộ cây con của quadtree mà các node lá của nó chứa trong bộ xử lý k.\\
\indent Cây LET được xác định đơn giản như sau: Gọi $n$ là node không chứa hạt nào trong k, $D(n)$ là kích cỡ hình vuông tương ứng với node $n$, $r(n)$ là khoảng cách ngắn nhất từ bất kì điểm nào trong n tới bất kì điểm nào trong k. Nếu hoặc \begin{itemize}
\item $(D(n)/r(n) < \theta$ và $(D(parent(n)))/r(parent(n)) \geq \theta$: tức là, $TM$ và $CM$ của node n có thể được dùng để tính lực tác động vào bất kì hạt nào trong k, nhưng node cha của n thì không.
\item $D(n)\geq r(n)$: ta cần duyệt node cha của n.
\end{itemize}
thì n là một phần của LET của tiến trình k. Giả sử n được lưu trong bộ xử lý j thì bộ xử lý j cần gửi n cho k.\\
\indent Giả sử $p=2^m$ là số bộ xử lý sử dụng. Mỗi bit thứ m của bộ xử lý xác định một lần chia đôi trực giao, bit bằng 0 nếu phần chia gán cho bộ xử lý nằm bở bên trái hoặc bên trên của đường chia đôi trực giao, bằng 1 nếu ngược lại.\\
\begin{figure}[!ht]
\centering
\includegraphics[scale=0.6]{spatialpartitioning}
\caption{\textit{Dựng cây LET}}\label{fig:}
\end{figure}
\indent Mã giả được thực hiện cho mỗi tiến trình như sau:\\
\textit{tính quadtree cục bộ T\\
   LET $=$ T\\
   for $i = 0$ to m-1            ... $p = 2^m$\\
       OTHERPROC $=$ MYPROC xor 2i\\     
             ... đẩy bít thứ i của MYPROC\\
       tính các tập con của LET mà các bộ xử lý trên nửa còn lại của đường chia i yêu cầu\\
       Gửi tập con này tới OTHERPROC\\
       Nhận tập con tương ứng từ OTHERPROC, và nhập vào cây LET\\
   end for\\
   Gỡ LET của các phần không cần thiết\\}
\paragraph{Tree partitioning} Cách tiếp cận này được goi là \textit{costzones} trong hệ thống bộ nhớ chia sẻ, \textit{hashed octtree} trong hệ thống bộ nhớ phân tán. Thuật toán làm việc tốt trên không gian 3-chiều. Ta sẽ thay việc phân nhỏ cây bằng việc phân nhỏ cây QuadTree.\\
Thuật toán cho bộ nhớ chia sẻ: 
\begin{itemize}
\item Ước lượng công việc cần thực hiện để tính lực tại các node lá. Nếu là lần xây dựng cây đầu tiên thì ước lượng theo chiều sâu của node trong cây, nếu ngược lại ta ước lượng từ lời gọi cuối cùng tới Barnes-Hut.
\item Phân tổng công việc trong các lá vào $p$ khối(costzones), lượng công việc ở mỗi khối là $W/p$. Khối có thể chứa các hình vuông không kề nhau. 
\end{itemize}
\begin{figure}[!ht]
\centering
\includegraphics[scale=0.65]{costzones}
\caption{\textit{Dùng các khối để hiển thị công việc của QuadTree vào 4 bộ xử lý, khối công việc được khoanh vòng.}}\label{fig:}
\end{figure}
Thuật toán cho bộ nhớ phân tán: Thuật toán sử dụng một cấu trúc dữ liệu phân tán được gọi là \textit{hashed octtree}. 
\begin{itemize}
\item Đầu tiên, ta kết hợp mỗi node của cây với một khóa (\textit{key})duy nhất trong cây quadtree. Xác định khóa như sau: $(x,y)$ là tọa độ tâm của hình vuông, ta coi x, y là các xâu bit. Key được tạo bằng cách đặt xen kẽ các bít với nhau từ phải sang trái và thêm 1 vào đầu bên trái.
\begin{figure}[!ht]
\centering
\includegraphics{key}
\caption{\textit{Xây dựng một key cho hashed quadtree}}\label{fig:}
\end{figure}
\item Sau đó, sử dụng hàm băm \textit{hash(key)} để gán mỗi khóa vào một địa chỉ toàn cục trong một bảng băm được lưu tại bộ nhớ toàn cục. Hàm băm \textit{hash(key)} là một mặt nạ bit đơn giản của $h$ bit cuối cùng của mỗi khóa. Do vậy, các mức $(h/2)+1$ của cây quadtree ($(h/3)+1$ của cây octree) có một giá trị duy nhất trong hàm băm. Mỗi mục của bảng băm gồm một con trỏ trỏ tới danh sách các hộp có cùng giá trị trong hàm băm, một danh sách các ô có mặt, dữ liệu khối lượng và tâm của khối.
\item Bảng băm được phân bố tới các bộ xử lý sử dụng kĩ thuật tương tự như \textit{costzones}. Giả sử $h=4$ sẽ có một ô trong bảng băm tương ứng với một ô trong 16 ô vuông tại mức 3 của cây quadtree, các khóa này sẽ xác định một thứ tự tuyến tính cho các ô. Ta cần chia 16 ô vuông này thành $p$ khối kề nhau để gán vào các bộ xử lý. Tương tự như \textit{costzones} cũng có các vùng không kề nhau cùng được gán vào một bộ xử lý.
\begin{figure}[!ht]
\centering
\includegraphics[scale=0.6]{hash}
\caption{\textit{Gán các mục của bảng băm vào 4 bộ xử lý.}}\label{fig:}
\end{figure}
\item Cuối cùng, cây được duyệt bằng cách gửi thông điệp để truy cập từ xa các phần của bảng băm.
\end{itemize}
\indent Việc song song thuật toán Barnes-Hut đã làm giảm thời gian thực hiện một cách đáng kể. Đây là các kết quả thực hiện phép tính trong vật lý học thiên thể sử dụng thuật toán song song Barnes-Hut trên mát tính Intel Delta như trên. Một lần thực hiện thuật toán Barnes-Hut, giả sử các hạt có phân bố đểu, tổng thời gian thực hiện là 114 giây. Khi các vật thể có phân bố không đều, thời gian chạt là 160 giây.[1]
